<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">










<meta name="description" content="在上一篇GCN的博文中重点讨论了图神经网络的逐层传播公式是如何推导的，然而，GCN的训练方式需要将邻接矩阵和特征矩阵一起放到内存或者显存里，在大规模图数据上是不可取的。其次，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现（比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的），这是GCN本身的巨大局限——Transductive Learnin">
<meta property="og:type" content="article">
<meta property="og:title" content="GNN系列三：GraphSAGE">
<meta property="og:url" content="http://yoursite.com/2019/09/03/GNN系列三：GraphSAGE/index.html">
<meta property="og:site_name" content="MARS">
<meta property="og:description" content="在上一篇GCN的博文中重点讨论了图神经网络的逐层传播公式是如何推导的，然而，GCN的训练方式需要将邻接矩阵和特征矩阵一起放到内存或者显存里，在大规模图数据上是不可取的。其次，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现（比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的），这是GCN本身的巨大局限——Transductive Learnin">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567500297/sage_plf9nb.png">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567501687/sage_bek2tt.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567507906/embedding_generation_k9cxvi.png">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567508665/Sample_gaezlu.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567510098/result_v3ocjt.jpg">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn1_mbpilf.png">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn2_oggn6e.png">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn3_pvbadv.png">
<meta property="og:image" content="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn4_nqx52k.png">
<meta property="og:updated_time" content="2019-10-24T02:13:44.428Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="GNN系列三：GraphSAGE">
<meta name="twitter:description" content="在上一篇GCN的博文中重点讨论了图神经网络的逐层传播公式是如何推导的，然而，GCN的训练方式需要将邻接矩阵和特征矩阵一起放到内存或者显存里，在大规模图数据上是不可取的。其次，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现（比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的），这是GCN本身的巨大局限——Transductive Learnin">
<meta name="twitter:image" content="https://res.cloudinary.com/leomars/image/upload/v1567500297/sage_plf9nb.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2019/09/03/GNN系列三：GraphSAGE/">





  <title>GNN系列三：GraphSAGE | MARS</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">MARS</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-schedule">
          <a href="/schedule/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-calendar"></i> <br>
            
            日程表
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/09/03/GNN系列三：GraphSAGE/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="MARS">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/messi.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="MARS">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">GNN系列三：GraphSAGE</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-09-03T14:33:33+08:00">
                2019-09-03
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/GNN/" itemprop="url" rel="index">
                    <span itemprop="name">GNN</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
                <a href="/2019/09/03/GNN系列三：GraphSAGE/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count gitment-comments-count" data-xid="/2019/09/03/GNN系列三：GraphSAGE/" itemprop="commentsCount"></span>
                </a>
              </span>
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>在上一篇GCN的博文中重点讨论了图神经网络的逐层传播公式是如何推导的，然而，GCN的训练方式需要将邻接矩阵和特征矩阵一起放到内存或者显存里，在大规模图数据上是不可取的。其次，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现（比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的），这是GCN本身的巨大局限——Transductive Learning——没法快速表示新节点，这限制了它在生产环境中应用。同年NIPS来了一篇使用Inductive Learning的GraphSAGE，解决了这个问题，这篇文章中将会详细讨论GraphSAGE。</p>
<a id="more"></a>
<p>Written By Mars at 2019/09/03 14:30   </p>
<p>Reference：<a href="https://mp.weixin.qq.com/s/1DHvLLysMU24dBeLzbSpUA" target="_blank" rel="noopener">Datawhale</a>, <a href="http://mp.weixin.qq.com/s?__biz=MzU5MzcwODE3OQ==&amp;mid=2247483988&amp;idx=1&amp;sn=4544f9ad8a8c1899a4dfa977796675c5&amp;chksm=fe0d17a8c97a9ebe337636c0497c27d425381acf43c81775b295629bc98e86c0350cdd036c85&amp;mpshare=1&amp;scene=1&amp;srcid=0903BoNPQwBynnlJgZrOQjLD&amp;sharer_sharetime=1567492943097&amp;sharer_shareid=77ebcd1040f5dcf26dd0ef1bfb7b4462#rd" target="_blank" rel="noopener">SimpleAI</a>, and <a href="http://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs" target="_blank" rel="noopener">Inductive Representation Learning on Large Graphs</a></p>
<h1 id="GCN回顾"><a href="#GCN回顾" class="headerlink" title="GCN回顾"></a>GCN回顾</h1><p>GCN的基本思想：  把一个节点在图中的高纬度邻接信息降维到一个低维的向量表示。</p>
<p>GCN的优点：  可以捕捉Graph的全局信息，从而很好地表示node的特征。</p>
<p>GCN的缺点：  Transductive learning的方式，需要把所有节点都参与训练才能得到node embedding，无法快速得到新节点的embedding。</p>
<p>得到新节点的embedding的难处：  要想得到新节点的表示，需要让新的Graph或者Subgraph去和已经优化好的node embedding去“对齐”。然而每个节点的表示都是受到其他节点的影响，因此添加一个节点，意味着许许多多与之相关的节点的表示都应该调整。这会带来极大的计算开销，即使增加几个节点，也要完全重新训练所有的节点。</p>
<p>因此需要换一种思路：既然新增的节点，一定会改变原有节点的表示，那么干嘛一定要得到每个节点的一个固定的表示呢？我们何不直接<strong>学习一种节点的表示方法</strong>。这样不管Graph怎么改变，都可以很容易地得到新的表示。</p>
<h1 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h1><h2 id="Inductive-learning-vs-Transductive-learning"><a href="#Inductive-learning-vs-Transductive-learning" class="headerlink" title="Inductive learning  vs Transductive learning"></a>Inductive learning  vs Transductive learning</h2><p>首先介绍一下什么是Inductive learning。与其他类型的数据不同，图数据中的每一个节点可以通过边的关系利用其他节点的信息，这样就产生了一个问题，如果训练集上的节点通过边关联到了测试集或者验证集的节点，那么在训练的时候能否用它们的信息呢? 如果训练时用到了测试集或验证集样本的信息（或者说，测试集和验证集在训练的时候是可见的），我们把这种学习方式叫做Transductive learning，反之，称为inductive learning。</p>
<p>显然，我们所处理的大多数机器学习问题都是Inductive learning， 因为我们刻意的将样本集分为训练/验证/测试集，并且训练的时候只使用训练集。然而，在GCN中，训练节点收集邻居信息的时候，用到了测试或者验证集样本，所以它是Transductive learning。</p>
<h2 id="Graph-SAmple-and-aggreGatE"><a href="#Graph-SAmple-and-aggreGatE" class="headerlink" title="Graph SAmple and aggreGatE"></a>Graph SAmple and aggreGatE</h2><p>GraphSAGE是一个Inductive框架，在具体实现中，训练时它仅仅保留训练样本到训练样本的边。<strong>Inductive learning 的优点是可以利用已知节点的信息为未知节点生成embedding。</strong></p>
<p>GraphSAGE 取自 Graph SAmple and aggreGatE，SAmple指如何对邻居个数进行采样，aggreGatE指拿到邻居的embedding之后如何汇聚这些embedding以更新自己的embedding信息。下图展示了GraphSAGE学习的一个过程：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567500297/sage_plf9nb.png" alt></p>
<ol>
<li><p>对邻居进行采样；</p>
</li>
<li><p>采样后的邻居embedding传到节点上来，并使用一个聚合函数聚合这些邻居信息以更新节点的embedding；</p>
</li>
<li>根据更新后的embedding预测节点的标签。</li>
</ol>
<h1 id="GraphSAGE"><a href="#GraphSAGE" class="headerlink" title="GraphSAGE"></a>GraphSAGE</h1><p><strong>基本思想：学习一个节点的信息是怎么通过其邻居节点的特征聚合而来的。</strong> 学习到这样的“聚合函数”，而本身就已知各个节点的特征和邻居关系，就可以很方便地得到一个新节点的表示。GCN等Transductive 的方法，学到的是每个节点的一个唯一确定的embedding； 而GraphSAGE方法学到的node embedding，是根据node的邻居关系的变化而变化的，也就是说，即使是旧的node，如果建立了一些新的link，那么其对应的embedding也会变化，而且也很方便地学到。</p>
<h2 id="Embedding-generation（前向传播算法）"><a href="#Embedding-generation（前向传播算法）" class="headerlink" title="Embedding generation（前向传播算法）"></a>Embedding generation（前向传播算法）</h2><p>这一节讨论的是如何给图中的节点生成（或者说更新）embedding，假设我们已经完成了GraphSAGE的训练，因此模型所有的参数（parameters）都已知了。具体来说，这些参数包括$K$个聚合器$AGGREGATEA_{k}, \forall k \in {1, \cdots ,K}$（见下图算法第4行）中的参数，这些聚合器被用来将邻居embedding信息聚合到节点上，以及一系列的权重矩阵$\mathbf{W}^{k}, \forall k \in\{1, \ldots, K\}$（下图算法第5行），这些权值矩阵被用作在模型层与层之间传播embedding的时候做非线性变换。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567501687/sage_bek2tt.jpg" alt></p>
<p>算法的主要部分为：</p>
<ul>
<li>line1 初始化每个节点embedding为每个节点的特征向量；</li>
<li>line3—-line6 对于每一个节点 $v$ 拿到它采样后的邻居embedding $h_{u}, u \in \mathcal{N}(v)$并将其聚合，这里的$\mathcal{N}(v)$表示对邻居采样根据聚合后的邻居embedding（$h_{N(v)}$）和自身embedding（$h_{v}$）通过一个非线性变换（$\sigma(\mathbf{W} \cdot \square)$）更新自身embdeding。</li>
</ul>
<p><strong>算法里的$K$这个比较难理解，$K$之前提到过，它既是聚合器的数量，也是权重矩阵的数量，还是网络的层数，这是因为每一层网络中聚合器和权重矩阵是共享的。</strong>网络的层数可以理解为需要最大访问到的邻居的跳数（hops），比如在Figure1中，红色节点的更新拿到了它一、二跳邻居的信息，那么网络层数就是2。为了更新红色节点，首先在第一层（$k=1$）我们会将蓝色节点的信息聚合到红色节点上，将绿色节点的信息聚合到蓝色节点上。在第二层（$k=2$）红色节点的embedding被再次更新，不过这次用的是更新后的蓝色节点embedding，这样就保证了红色节点更新后的embedding包括蓝色和绿色节点的信息。</p>
<p>这里需要注意的是，每一层的node的embedding都是由上一层生成的，跟本层的其他节点无关。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567507906/embedding_generation_k9cxvi.png" alt></p>
<h2 id="采样-Sample-算法"><a href="#采样-Sample-算法" class="headerlink" title="采样 (Sample) 算法"></a>采样 (Sample) 算法</h2><p>GraphSAGE采用了定长抽样的方法，具体来说，定义需要的邻居个数$S$，然后采用有放回的重采样/负采样方法达到$S$。保证每个节点（采样后的）邻居个数一致。这样做是为了把多个节点以及他们的邻居拼成Tensor送到GPU中进行批训练。</p>
<p>这里作者的做法是设置一个定值，每次选择邻居的时候就是从周围的直接邻居（一阶邻居）中均匀地采样固定个数个邻居。但是这里有一个疑问，每次都只是从其一阶邻居聚合信息，为何作者说：随着迭代，可以聚合越来越远距离的信息呢？</p>
<p>虽然在聚合时仅仅聚合了一个节点邻居的信息，但该节点的邻居，也聚合了其邻居的信息，这样，在下一次聚合时，该节点就会接收到其邻居的邻居的信息，也就是聚合到了二阶邻居的信息。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567508665/Sample_gaezlu.jpg" alt></p>
<p>由上图（为了图的简洁，这里假设只随机聚合两个邻居）可以看出，层与层之间，确实都是一阶邻居的信息在聚合：</p>
<ul>
<li><p>图中的“1层”，节点$v$聚合了“0层”的两个邻居的信息，$v$的邻居$u$也是聚合了“0层”的两个邻居的信息。</p>
</li>
<li><p>到了图中的“2层”，可以看到节点$v$通过“1层”的节点$u$，扩展到了“0层”的二阶邻居节点。</p>
</li>
</ul>
<p>因此，在聚合时，聚合$K$次，就可以扩展到$K$阶邻居。在GraphSAGE的实践中，作者发现，$K$不必取很大的值，当$K=2$时，效果就非常好，也就是只用扩展到2阶邻居即可。</p>
<p>至于邻居的个数，文中提到$S1×S2&lt;=500$，即两次扩展的邻居数之和小于等于500，大约每次只需要扩展20来个邻居即可。这也是合情合理，例如在现实生活中，对你影响最大就是亲朋好友，这些属于一阶邻居，然后可能你偶尔从他们口中听说一些他们的同事、朋友的一些故事，这些会对你产生一定的影响，这些人就属于二阶邻居。但是到了三阶，可能基本对你不会产生什么影响了，例如你听你同学说他同学听说她同学的什么事迹，是不是很绕口，因为你基本不会听到这样的故事，你所接触到的、听到的、看到的，基本都在“二阶”的范围之内。</p>
<h2 id="聚合函数（Aggregator）的选择"><a href="#聚合函数（Aggregator）的选择" class="headerlink" title="聚合函数（Aggregator）的选择"></a>聚合函数（Aggregator）的选择</h2><p>GraphSAGE 提供了多种聚合器，实验中效果最好的平均聚合器（mean aggregator），平均聚合器的思想很简单，每个维度取对邻居embedding相应维度的均值，这个和GCN的做法基本一致（GCN实际上用的是求和）：</p>
<ul>
<li>GCN aggregator：这个跟mean aggregator十分类似，把这个公式，去替换前面给的Algorithm1中的第4，5行。实际上，这个几乎就是GCN中的聚合方式。公式如下：</li>
</ul>
<script type="math/tex; mode=display">
\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W} \cdot \operatorname{MEAN}\left(\left\{\mathbf{h}_{v}^{k-1}\right\} \cup\left\{\mathbf{h}_{u}^{k-1}, \forall u \in \mathcal{N}(v)\right\}\right)\right.</script><ul>
<li><p>LSTM aggregator：使用LSTM来encode邻居的特征。 这里忽略掉邻居之间的顺序，即随机打乱，输入到LSTM中；</p>
</li>
<li><p>Pooling aggregator：把各个邻居节点单独经过一个MLP得到一个向量，最后把所有邻居的向量做一个element-wise的max-pooling或者什么其他的pooling。公式如下：</p>
<script type="math/tex; mode=display">
\operatorname{AGGREGATE}_{k}^{\text {pool }}=\max \left(\left\{\sigma\left(\mathbf{W}_{\text {pool }} \mathbf{h}_{u_{i}}^{k}+\mathbf{b}\right), \forall u_{i} \in \mathcal{N}(v)\right\}\right)</script></li>
</ul>
<h2 id="GraphSAGE的参数学习"><a href="#GraphSAGE的参数学习" class="headerlink" title="GraphSAGE的参数学习"></a>GraphSAGE的参数学习</h2><p>在上面的过程中，我们需要学习各个聚合函数的参数，因此需要设计一个损失函数。 损失函数是设计是根据目标任务来的，可以是无监督的，也可以是有监督的。</p>
<p>在有监督的情况下，可以使用每个节点的预测label和真实label的交叉熵作为损失函数。</p>
<p>在无监督的情况下，可以假设相邻的节点的输出embedding应当尽可能相近，因此可以设计出如下的损失函数：</p>
<script type="math/tex; mode=display">
J_{\mathcal{G}}\left(\mathbf{z}_{u}\right)=-\log \left(\sigma\left(\mathbf{z}_{u}^{\top} \mathbf{z}_{v}\right)\right)-Q \cdot \mathbb{E}_{v_{n} \sim P_{n}(v)} \log \left(\sigma\left(-\mathbf{z}_{u}^{\top} \mathbf{z}_{v_{n}}\right)\right)</script><p>其中$z_{u}$是节点$u$的输出embedding，$v$是节点$u$的邻居（这里邻居是广义的，比如说如果$v$和$u$在一个定长的随机游走中可达，那么我们也认为他们相邻），$P_{n}$是负采样分布，$Q$是负采样的样本数量，所谓负采样指我们还需要一批不是$v$邻居的节点作为负样本，那么上面这个式子的意思是相邻节点的embedding的相似度尽量大的情况下保证不相邻节点的embedding的期望相似度尽可能小。</p>
<h1 id="实验"><a href="#实验" class="headerlink" title="实验"></a>实验</h1><p><img src="https://res.cloudinary.com/leomars/image/upload/v1567510098/result_v3ocjt.jpg" alt></p>
<h1 id="GraphSAGE-amp-GCN"><a href="#GraphSAGE-amp-GCN" class="headerlink" title="GraphSAGE &amp; GCN"></a>GraphSAGE &amp; GCN</h1><p>从直观上去看，我一开始觉得GraphSAGE和GCN截然不同，其实只是论文作者的介绍的角度不同，实际上两者的本质上没有很大差别。</p>
<p>GCN：</p>
<script type="math/tex; mode=display">
H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)\\
H^{(l+1)}=\sigma\left( \hat{A} H^{(l)} W^{(l)}\right)</script><p>这个公式的内部，画成矩阵相乘的形式是这样的：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn1_mbpilf.png" alt></p>
<p>其中，$A$是$n×n$维，$H$是$n×m$维，$W$则是$m×u$维。$n$就是节点个数，$m$则是节点特征的维度，$u$就是神经网络层的单元数。</p>
<p>$\hat{A} \times H$：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn2_oggn6e.png" alt></p>
<p>$\hat{A}$（矩阵的第$i$行和$H$矩阵的第$j$列对应元素相乘在求和就得到$Q$矩阵的$(i,j)$个元素。这都是最基本的线性代数，不妨再仔细看看图中高亮的那几个向量的内部：</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn3_pvbadv.png" alt></p>
<p>由上图可以发现，GCN的这一步，跟GraphSAGE是一样的思想，都是把邻居的特征做一个聚合（aggregation）。</p>
<p><img src="https://res.cloudinary.com/leomars/image/upload/v1567510828/gcn4_nqx52k.png" alt></p>
<p>所以，都是Aggregate！</p>
<h1 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h1><p>GraphSAGE的mean-aggregator跟GCN十分类似。在GCN中，是直接把邻居的特征进行求和，而实际不是$A \times H$，而是$\hat{A} \times H$，$\hat{A}$是归一化的$A$，所以上图中的邻居关系向量不应该是0，1构成的序列，而是归一化之后的结果，所以跟$H$的向量相乘之后，相当于是“求平均”。GraphSAGE进一步拓展了“聚合”的方法，提出了LSTM、Pooling等聚合方式，不是简单地求平均，而是更加复杂的组合方式，所以有一些效果的提升。</p>
<p>至于说为什么GCN是Transductive，为什么要把所有节点放在一起训练？我不一定要把所有节点放在一起训练，一个个节点放进去训练也是可以的。无非是如果想得到所有节点的embedding，那么GCN可以把整个Graph放进去，直接得到所有节点的embedding，还可以直接进行节点分类、边的预测等任务。</p>
<p>其实，通过GraphSAGE得到的节点的embedding，在增加了新的节点之后，旧的节点也需要更新，这个是无法避免的，因为，新增加节点意味着环境发生了改变，那之前的节点的表示自然也应该有所调整。只不过，对于旧的节点，可能新增一个节点对其影响微乎其微，所以可以暂且使用原来的embedding，但如果新增了很多，极大地改变的原有的Graph结构，那么就只能全部更新。从这个角度去想的话，GraphSAGE也只不过生成新节点embedding的过程，实施起来相比于GCN更加灵活方便。学习到了各种的聚合函数之后，其实就不用去计算所有节点的embedding，而是当需要去考察哪些节点，就现场去计算，这种方法的迁移能力也很强，在一个Graph上学到了节点的聚合方法，到另一个新的类似的Graph上就可以直接使用。</p>
<p>GraphSAGE采用采样的机制，克服了GCN训练时内存和显存上的限制，使得图模型可以应用到大规模的图结构数据中，是目前几乎所有工业上图模型的雏形。然而，每个节点这么多邻居，采样能否考虑到邻居的相对重要性呢？或者在聚合计算中能否考虑到邻居的相对重要性? 这个问题在下一篇博文Graph Attentioin Networks（GAT）中做详细的讨论。</p>
<h1 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h1><p><a href="https://github.com/JyZhang10Mars/YooChooseGraphSAGE" target="_blank" rel="noopener">PyTorch-Geometric-YooChoose</a></p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/09/01/GNN系列二：GCN/" rel="next" title="GNN系列二：GCN">
                <i class="fa fa-chevron-left"></i> GNN系列二：GCN
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/09/05/论文笔记：Graph-Convolutional-Networks-with-Argument-Aware-Pooling-for-Event-Detection/" rel="prev" title="论文笔记：Graph Convolutional Networks with Argument-Aware Pooling for Event Detection">
                论文笔记：Graph Convolutional Networks with Argument-Aware Pooling for Event Detection <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      
        <div id="gitment-container"></div>
      
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/images/messi.jpg" alt="MARS">
            
              <p class="site-author-name" itemprop="name">MARS</p>
              <p class="site-description motion-element" itemprop="description">自由是一种信仰</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">11</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">4</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/JyZhang10Mars" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="jyzhang.mars@gmail.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#GCN回顾"><span class="nav-number">1.</span> <span class="nav-text">GCN回顾</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#概述"><span class="nav-number">2.</span> <span class="nav-text">概述</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#Inductive-learning-vs-Transductive-learning"><span class="nav-number">2.1.</span> <span class="nav-text">Inductive learning  vs Transductive learning</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#Graph-SAmple-and-aggreGatE"><span class="nav-number">2.2.</span> <span class="nav-text">Graph SAmple and aggreGatE</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#GraphSAGE"><span class="nav-number">3.</span> <span class="nav-text">GraphSAGE</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#Embedding-generation（前向传播算法）"><span class="nav-number">3.1.</span> <span class="nav-text">Embedding generation（前向传播算法）</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#采样-Sample-算法"><span class="nav-number">3.2.</span> <span class="nav-text">采样 (Sample) 算法</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#聚合函数（Aggregator）的选择"><span class="nav-number">3.3.</span> <span class="nav-text">聚合函数（Aggregator）的选择</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#GraphSAGE的参数学习"><span class="nav-number">3.4.</span> <span class="nav-text">GraphSAGE的参数学习</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#实验"><span class="nav-number">4.</span> <span class="nav-text">实验</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#GraphSAGE-amp-GCN"><span class="nav-number">5.</span> <span class="nav-text">GraphSAGE &amp; GCN</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#总结"><span class="nav-number">6.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#代码实现"><span class="nav-number">7.</span> <span class="nav-text">代码实现</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">MARS</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Pisces</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "box";
      
          pbOptions.boxForm = "horizontal";
      
          pbOptions.position = "bottomCenter";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
          flOptions.iconStyle = "box";
      
          flOptions.boxForm = "horizontal";
      
          flOptions.position = "middleRight";
      
          flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>

  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
